package com.cheng.algorithm.search;

/**
 * @User Administrator
 * @Classname BinarySearch
 * @Project Data-structure-and-algorithm
 * @Description 二分查找：
 * 二分查找的思路分析：使用二分查找前提该数组是有序的
 * 1.首先确定该数组的中间的下标mid= (left +right)/ 2，
 * 2.然后让需要查找的数findval和arr[mid]比较
 *   2.1 findval > arr[mid]，说明你要查找的数在mid的右边,因此需要递归的向右查找
 *   2.2 findval < arr[mid],说明你要查找的数在mid的左边,因此需要递归的向左查找
 *   2.3 findval == arr[mid]说明找到，就返回
 * 3.什么时候我们需要结束递归
 *   1)找到就结束递归
 *   2)当left> right,表明递归完整个数组，仍然没有找到findval，就需要退出递归
 * @Author wpcheng
 * @Create 2021-08-16-9:41
 * @Version 1.0
 */
public class BinarySearch {
    public static void main(String[] args) {
        int arr[] = {1, 8, 10, 89, 106, 256};
        int i = binarySearch(arr, 0, arr.length - 1, 106);
        if (i == -1){
            System.out.println("没找到");
        }else {
            System.out.println("查找到下标为："+i+" 的数");
        }
    }
    /**
     *
     * @param arr       数组
     * @param left      左边的索引
     * @param right     右边的索引
     * @param findVal   要查找的数
     * @return  找到返回下标，没找到返回-1
     */
    public static int binarySearch(int[] arr,int left,int right,int findVal){
        int mid = (left + right) / 2;
        int midVal = arr[mid];
        //当left> right,表明递归完整个数组，仍然没有找到findval，就需要退出递归
        if (left > right){
            return -1;
        }
        //findval >arr[mid]，说明你要查找的数在mid的右边,因此需要递归的向右查找
        if (findVal > midVal){
            return binarySearch(arr,mid+1,right,findVal);
        //findval<arr[mid],说明你要查找的数在mid的左边,因此需要递归的向左查找
        }else if (findVal < midVal){
            return binarySearch(arr,left,mid-1,findVal);
        //findval == arr[mid]说明找到，就返回
        }else {
            return mid;
        }

    }


}
